前幾天我們花了很多篇幅在講樹狀結構，今天要進到新單元 圖形結構 了~

圖形結構(Graph)是什麼

圖形結構是以 頂點 (Vertix)和 邊 (Edge) 所組成的集合

Graph Theory或 拓樸理論(Topology)源自於 Koenigsberg bridge 問題 有興趣可以點開來看 ~ 這邊偏向離散數學的範疇就不細講了
跟樹狀結構差別最大的地方在於，圖形結構的頂點可以任意連接，甚至形成迴圈

基本名詞

1. 頂點 (Vertices) : 圖中的節點

2. 邊 (Edge) : 兩頂點間的連線叫做「邊」

3. 圖 (Graph) : 圖是由頂點和邊組合成的集合，記為 G(E,V)

   • V(G) : 所有頂點組成的集合
   • E(G) : 所有邊組成的集合

4. 有向圖 : 邊具有方向性，例如<v1,v2> 其中v1代表前端，v2代表尾端
   <v1,v2> ≠ <v2,v1>

5. 無向圖 : 邊不具方向性，(v1,v2)=(v2,v1)
   

6. 完整圖 :

   • 有向圖 : 假設有n個頂點，有 n(n-1) 個邊，為「有向完整圖」
   • 無向圖 : 假設有n個頂點，有 n(n-1)/2 個邊，為完整圖

7. 多重圖形 : 多重圖形不是圖，兩個頂點間有多條邊即為多重圖形
   

8. 相鄰 (adjacent)：若兩個頂點之間有邊直接相連，稱這兩個頂點互為相 鄰。例如邊 (v1, v2)，則 v1 與 v2 相鄰。

9. 附著 (incident) :邊 e 連接頂點 v1 和 v2,則稱邊 e 「附著」於 v1 和 v2,或稱 v1、v2 與邊 e 相互附著
   如附著在 頂點 5的邊有 (1,5),(4,5),(5,6)
   

10. 分支度 (degree) : 一個頂點所連接的邊數量
    公式 : 當圖有n個頂點，e個邊，di為頂點i的分支度，

    • 有向圖的分支度分為內分支度和外分支度
      • 內分支度 (in - degree ) : 指向自己的邊數
      • 外分支度 (out - degree) : 自己指出去的邊數

11. 連通 (connected) : 兩個頂點之間存在至少一條路徑可以互相到達，稱這兩個頂點是連通的

12. 路徑(path) : 路徑是可以由一個邊或數個邊所組成的，從某個頂點出發，經過一連串的邊，到達另一個頂點所形成的頂點序列。如果路徑中所有頂點都不重複，稱為「簡單路徑(Simple Path)」

13. 子圖(subgraph) :
    設圖 G 由頂點集合 V(G) 與邊集合 E(G) 組成
    若另一個圖 G' 滿足 V(G') ⊆ V(G) 且 E(G') ⊆ E(G)
    則稱 G' 為 G 的子圖。
    換句話說，子圖的頂點必須是原圖頂點的子集合，而且子圖的邊也必須是原圖中確實存在的邊，不能包含原圖沒有的連線

圖形表示法

最常見的有相鄰矩陣表示法 (Adjacency Matrix)、相鄰串列表示法 (Adjacency List)

相鄰矩陣(Adjacency Matrix)

假設圖有 n 個頂點，則使用 n x n 的矩陣來存放
matrix[i][j]= 1 代表頂點 i 和頂點 j 之間有邊相連，0 代表沒有

對應的相鄰矩陣:

求分支度:

• 無向圖: 任意頂點i的分支度為，或是各列 (各行) 的和，C的分支度為1+0+0+1=2
  

• 有向圖
  

  • 內分支度 : 各列之和
  • 外分支度 : 各行之和

#include <vector>
using namespace std;

// 用二維陣列表示相鄰矩陣,4個頂點
vector<vector<int>> graph(4, vector<int>(4, 0));

void addEdge(int u, int v) {
    graph[u][v] = 1;
    graph[v][u] = 1;  // 無向圖,兩個方向都要設定
}

相鄰串列(Adjacency List)

每個頂點對應一個串列(或陣列)，存放與它相鄰的所有頂點

練習題

圖 G 的頂點集合 V(G) = {1, 2, 3, 4, 5},邊集合 E(G) = {(1,2), (2,3), (3,4)},請問下列哪一個是 G 的合法子圖?
(A ) 頂點 {1, 2, 5},邊 {(1,2), (1,5)}
(B ) 頂點 {1, 2, 3},邊 {(1,2), (2,3)}
(C ) 頂點 {1, 3},邊 {(1,3)}

參考資料和書籍

1. 資料結構初學指引 : 入門精要版(第四版)
2. https://zh.wikipedia.org/zh-tw/%E9%87%8D%E5%9B%BE
3. https://zh.wikipedia.org/zh-tw/%E6%9F%AF%E5%B0%BC%E6%96%AF%E5%A0%A1%E4%B8%83%E6%A1%A5%E9%97%AE%E9%A2%98
4. https://zh.wikipedia.org/wiki/%E5%9B%BE%E8%AE%BA
5. https://medium.com/@amber.fragments/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-%E5%AD%B8%E7%BF%92%E7%AD%86%E8%A8%98-7-graph-%E5%9C%96-d4359fb6f19a